package william.mergesort;

/**
 * @author ZhangShenao
 * @date 2024/1/25
 * @description <a href="https://mhibncatc0.feishu.cn/docx/C9bmdDpj0otd41xu75fcG1RHnGc">...</a>
 */
public class LCR_170_交易逆序对的总数 {
    /**
     * 本质上是针对数组中的每一个数，求后面有多少个数比它小。可以借助归并排序的思想。
     * 找到数组的中点，将整个数组分为左右两个部分。
     * 分别使左、右两个数组有序，并在这个过程中计算左、右两个数组的逆序对的数量。
     * 将左、右两个数组合并成一个整体有序数组，并计算此过程中产生的逆序对数量。在合并过程中：
     * - 从右至左（从大到小进行比较）
     * - 如果右组数>左组数，则无逆序对产生，直接拷贝右组数。
     * - 如果右组数=左组数，也无逆序对产生，直接拷贝右组数，继续检查左组数。
     * - 如果左组数>右组数，则产生了逆序对，右组从当前数开始，一直到数组第一个元素，都构成了逆序对。
     * - 数组总逆序对数 = 左数组逆序对数 + 右数组逆序对数 + 当前数组合并过程中产生的逆序对数
     */
    public int reversePairs(int[] record) {
        //边界条件校验
        if (record == null || record.length < 2) {
            return 0;
        }

        //调用递归处理
        return reversePairsRecursion(record, 0, record.length - 1);
    }

    /**
     * 递归处理
     * 将数组record[L,R]范围内处理成有序,并返回次范围内逆序对的数量
     */
    private int reversePairsRecursion(int[] record, int L, int R) {
        //递归终止条件
        if (L == R) {
            return 0;
        }

        //找到数组中点,将数组划分成左、右两部分
        int M = L + ((R - L) >> 1);

        //分别将左、右两部分数组处理成有序,并获取两部分的逆序对数量
        int lCount = reversePairsRecursion(record, L, M);
        int rCount = reversePairsRecursion(record, M + 1, R);

        //将左、右两个有序数组合并成一个整体有序数组,并计算此过程中产生的逆序对数量
        int mCount = merge(record, L, M, R);

        //最终逆序对总数=左数组逆序对数+右数组逆序对数+合并过程中计算出的逆序对数
        return lCount + rCount + mCount;
    }

    /**
     * 递归处理
     * 将record[L,M]和record[M+1,R]两个有序数组,合并成一个整体有序数组,并返回该过程中的逆序对数量
     */
    private int merge(int[] record, int L, int M, int R) {
        //创建临时数组用于拷贝元素
        int len = R - L + 1;
        int[] tmp = new int[len];

        //初始化索引
        int l = M;
        int r = R;
        int i = len - 1;
        int count = 0;

        //从大到小拷贝元素
        while (l >= L && r >= (M + 1)) {
            //如果右组数>=左组数,则不产生逆序对,直接拷贝右组数
            if (record[r] >= record[l]) {
                tmp[i--] = record[r--];
            } else { //如果左组数>右组数,则产生逆序对,逆序对的范围是从右组开始到当前右组位置
                //累加逆序对数量,并拷贝左组数
                count += (r - M);   //r-(M+1)+1=r-M-1+1=r-M
                tmp[i--] = record[l--];
            }
        }

        //当其中一组已经拷贝完成,后面就无逆序对产生,直接拷贝剩余元素
        while (l >= L) {
            tmp[i--] = record[l--];
        }
        while (r >= (M + 1)) {
            tmp[i--] = record[r--];
        }

        //将临时数组拷贝回原数组
        for (i = 0; i < len; i++) {
            record[L + i] = tmp[i];
        }

        //返回逆序对数量
        return count;
    }
}
